package com.graph;

import java.util.*;

public class MinPath {

    static class Node{
        int id;
        int value;
        List<Line> lines;
        //记录的路径
        Node preNode;
        Node nextNode;

        public Node(int id){
            this.id = id;
        }

        public void addLine(Line line){
            if(lines == null){
                lines = new ArrayList<>();
            }
            lines.add(line);
        }

        @Override
        public String toString() {
            return id + "号节点";
        }
    }

    static class Line{
        //是否是有向线段
        boolean hasDir;
        Node start;
        Node end;
        int value;

        public Line(Node start,Node end,int value){
            this.start = start;
            this.end = end;
            this.value = value;
        }
    }

    static class TwoTuple<U,V>{
        U first;
        V second;
        TwoTuple(U first,V second){
            this.first = first;
            this.second = second;
        }
    }

    //最短路径算法一,  提供找到起点到终点路径的深度优先搜索算法，无权和有权     无圈，有圈(需要额外标记)，（负值圈除外）皆可适应 :复杂度:领接表长度 E + 节点数量 V
    public static void findMinPathInNoCircleGraph(Node startNode, Node endNode){

        TwoTuple<Boolean,Integer> res = innerFindMinPathInNoCircleGraph(startNode,endNode);

        List<Node> nodeList = new ArrayList<>();
        nodeList.add(startNode);
        while(startNode.nextNode != null){
            nodeList.add(startNode.nextNode);
            startNode = startNode.nextNode;
        }

        System.out.println("最短路径长"+res.second);
        System.out.println(nodeList);

    }

    private static TwoTuple<Boolean,Integer> innerFindMinPathInNoCircleGraph(Node startNode, Node endNode) {

        List<Line> lines = startNode.lines;

        if(startNode == endNode){
            return new TwoTuple<>(true,0);
        }
        if(lines == null){
            return new TwoTuple<>(false,0);
        }

        boolean res = false;
        int distance = Integer.MAX_VALUE;

        for(Line line : lines){
            TwoTuple<Boolean,Integer> tuple = innerFindMinPathInNoCircleGraph(line.end,endNode);
            if(tuple.first){
                res = true;
                int tmp = tuple.second + line.value;
                if(tmp < distance){
                    distance = tmp;
                    startNode.nextNode = line.end;
                }

            }
        }
        return new TwoTuple<>(res,distance);
    }


    /**
     * 最短路径算法二，计算出所有点到源点的最短距离，针对有圈无权图的最短路径算法。
     *
     * 算法无法使用拓扑路径，因为处于有圈图中
     *
     * 算法给出广度优先的实现。
     * 深度优先的算法并不合适求这种算所有点的需求 ：因为深度优先算法擅长收集最后一个开始扩展向前的数据（递归），不适合收集这种需要熟知之前数据的需求。
     *
     * 深度优先算法由于无法在第一次遍历到某点时就一定求出某一点的最短距离，想要在过程中计算出所有点到源点的距离，必须再次经过这一点，并且再次更新所有相关的点。
     *
     * 由于广度优先算法 和 无权，保证了点在第一次被遍历到时，其距离一定是最小的，所以可以通过广度优先遍历所有邻接表，并直接更新其最短路径。有尝试重复更新的直接失败。
     *
     *
     */
    public static void findMinPathInCircleNoWeight(Node startNode, Node endNode){

        Queue<Node> queue = new LinkedList<>();
        queue.offer(startNode);
        startNode.value = 0;

        while(!queue.isEmpty()){
            Node node = queue.poll();
            if(node.lines == null){
                continue;
            }
            for(Line line : node.lines){
                if(line.end.value == 0) {
                    line.end.value = node.value + 1;
                    line.end.preNode = node;
                    queue.offer(line.end);
                }
            }
        }

        System.out.println("最短路径长度:" + endNode.value);
        System.out.println("最短路径反向:");

        Node tmp = endNode;
        while(tmp != null){
            System.out.println(tmp.id);
            tmp = tmp.preNode;
        }



    }

    /**
     * 针对有圈有权图的最短路径算法
     * 这里先练习二叉堆的decrease值的方法。
     *
     * 相比有圈无权算法，由于第一次广度优先遍历到的时候，不一定能够保证目前的距离是最短距离。所以，每次选择所有候选者中距离最小的候选者，因为只有它能够保证该候选者现在对应的路径长度是最短的。
     * @param startNode
     * @param endNode
     */
    public static void findMinPathInCircleHasWeight(Node startNode, Node endNode){

        //PriorityQueue<Node> queue = new PriorityQueue();


    }

    /**
     *
     *
     * 有圈有权有负值的算法，这种情况下没办法，因为并没有一种选取方法能够保证选取的路径的长度一定是最小的。
     * 只能广度优先遍历，有可能出现
     *
     *
     * @param startNode
     * @param endNode
     */
    public static void findMinPathInCircleHasWeightAndNegative(Node startNode, Node endNode){



    }


    public static void main(String[] args){

        Node node1 = new Node(1);
        Node node2 = new Node(2);
        Node node3 = new Node(3);
        Node node4 = new Node(4);
        Node node5 = new Node(5);
        Node node6 = new Node(6);
        Node node7 = new Node(7);
        Node node8 = new Node(8);
        Node node9 = new Node(9);
        Node node10 = new Node(10);

        Line line12 = new Line(node1,node2,1);
        Line line13 = new Line(node1,node3,1);
        Line line25 = new Line(node2,node5,1);
        Line line58 = new Line(node5,node8,1);
        Line line810 = new Line(node8,node10,1);
        Line line26 = new Line(node2,node6,1);
        Line line610 = new Line(node6,node10,1);
        Line line36 = new Line(node3,node6,1);
        Line line34 = new Line(node3,node4,1);
        Line line37 = new Line(node3,node7,1);
        Line line79 = new Line(node7,node9,1);
        Line line910 = new Line(node9,node10,1);

        node1.addLine(line12);
        node1.addLine(line13);

        node2.addLine(line25);
        node2.addLine(line26);

        node3.addLine(line34);
        node3.addLine(line36);
        node3.addLine(line37);

        node5.addLine(line58);

        node6.addLine(line610);

        node7.addLine(line79);

        node8.addLine(line810);

        node9.addLine(line910);

        //findMinPathInUnWeightedGraph(node1,node9);
        findMinPathInCircleNoWeight(node1,node10);

    }


}
